import java.util.*;

class hashCmp {
    private int val;

    public hashCmp(int val) {
        this.val = val;
    }

    @Override
    public int hashCode() {
        return super.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return super.equals(obj);
    }


}

public class text_oj {


    public static void main112(String[] args) {
        HashSet<hashCmp> h = new HashSet<>();
        hashCmp n1 = new hashCmp(1);
        h.add(n1);
        System.out.println(h.contains(n1));
    }

    public static int singleNumbe0r1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                set.remove(nums[i]);
            } else {
                set.add(nums[i]);
            }
        }
        Integer[] arr = new Integer[set.size()];
        set.toArray(arr);
        return arr[0].intValue();
    }

    public static int numJewelsInStones(String jewels, String stones) {

        Set<Character> Jewels = new TreeSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            Jewels.add(jewels.charAt(i));
        }
        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            if (Jewels.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }

    public static String findBreakKeyBoard(String rightS, String errorS) {
        StringBuilder targetS = new StringBuilder();
        Set<Character> errorSet = new HashSet<>();
        Set<Character> end = new HashSet<>();
        rightS = rightS.toUpperCase();
        errorS = errorS.toUpperCase();

        for (int i = 0; i < errorS.length(); i++) {
            errorSet.add(errorS.charAt(i));
        }
        for (int i = 0; i < rightS.length(); i++) {
            if (!errorSet.contains(rightS.charAt(i)) && !end.contains(rightS.charAt(i))) {
                end.add(rightS.charAt(i));
                targetS.append(rightS.charAt(i));
            }
        }
        return targetS.toString();
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        Map<Node, Node> map = new HashMap<>();
        Node tmp = head;
        Node connectN = null;//用来链接性链表
        Node newHead = null;
        // 创建复制的next链表
        while (tmp != null) {
            Node newN = new Node(tmp.val);
            map.put(tmp, newN);
            if (newHead == null) {//链接链表
                newHead = newN;
                connectN = newN;
            } else {
                connectN.next = newN;
                connectN = connectN.next;
            }
            tmp = tmp.next;
        }
        connectN.next = null;//手动为新链表结尾
        tmp = head;
        // map.get得到对应的新节点
        while (tmp != null) {//将random去链接
            Node tmpN = map.get(tmp);//得到的是创建的新节点
            Node tmpR = map.get(tmp.random);//得到tmp的随机链表对应的新创建的链表
            tmpN.random = tmpR;

            tmp = tmp.next;
        }
        return newHead;
    }

    public static List<String> topKFrequent(String[] words, int k) {
        //使用map k存储string V 储存数字
        Map<String, Integer> map = new HashMap<>();

        //遍历数组 储存每个单词出现的次数
        for (int i = 0; i < words.length; i++) {
            if (!map.containsKey(words[i])) {//没有储存这个string
                map.put(words[i], 1);
            } else {//包含
                map.put(words[i], map.get(words[i]) + 1);//将V加一
            }
        }
        List<String> strK = new LinkedList<>();
        //找到前k个大的string
        for (int i = 0; i < k; i++) {//遍历一次找到一个最大值
            int max = 0;
            String tmpS = "";//map没有对应的给V 会K的方法所以要自己记录
            for (int j = 0; j < words.length; j++) {
                if (map.containsKey(words[j]) && map.get(words[j]) > max) {//得到单词的出现次数 和对应的字符串
                    max = map.get(words[j]);
                    tmpS = words[j];
                } else if (map.containsKey(words[j]) && map.get(words[j]) == max) { //相等的情况 根据首字符的比较
                    if (words[j].compareTo(tmpS) < 0) {
                        max = map.get(words[j]);
                        tmpS = words[j];
                    }

//                    System.out.println("aa".compareTo("a"));

                }
            }
            strK.add(tmpS);
            map.remove(tmpS);
        }
        return strK;
    }

    public static boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            } else {
                set.add(nums[i]);
            }
        }
        return false;
    }

    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        boolean flag = false;
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (Math.abs(i - map.get(nums[i])) <= k) {
                    flag = true;
                }
                map.remove(nums[i]);//删除最先插入的值
                map.put(nums[i], i);//插入现在这个
            } else {
                map.put(nums[i], i);//K = 值 V = 下表
            }
        }
        return flag;
    }

    public static void ma1in(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println(containsDuplicate(nums));
        System.out.println(containsNearbyDuplicate(nums, 3));
    }

    public static void main2(String[] args) {
        String[] h = {"aaa", "aa", "a"};
        String[] hh = {"i", "love", "leetcode", "i", "love", "coding"};
        String[] hhh = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        String[] hhhh = {"i", "love", "leetcode", "i", "love", "coding"};
//        System.out.println(topKFrequent(hh, 2));
//        System.out.println(topKFrequent(hhh, 4));
//        System.out.println(topKFrequent(hhhh, 3));
        System.out.println(topKFrequent(h, 1));
      /*  text_oj a = new text_oj();
        System.out.println(a.copyRandomList(null));*/
    }

    public static void maain(String[] args) {
        String text = "7_This_is_a_test";
        String txt1 = "_hs_s_a_es";
        System.out.println(findBreakKeyBoard(text, txt1));
    }

    public static void main1(String[] args) {
        int[] arr = {1, 1, 2, 2, 3, 4, 4};
//        System.out.println(singleNumber(arr));
        String jewels = "aA";
        String stones = "aAAbbbb";
        System.out.println(numJewelsInStones(jewels, stones));
    }

}
